package hot_100;

/**
 * @author: Darven
 * @createTime: 2025-10-03  01:19
 * @description: TODO
 */
public class P148 {

    /**
     * 归并排序（递归方法）
     * 通过分治，找到链表中间，分到最小块，最小快进行比较，进行链表连接即可（合并有序链表）
     * */
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }

        // 快慢指针进行查询中间链表，因为快指针是慢指针的2倍，快指针到达时，慢指针刚好在中间
        ListNode slow=head;
        ListNode fast=head.next;

        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }

        ListNode index=slow.next;
        slow.next=null;

        ListNode left = sortList(head);
        ListNode right = sortList(index);

        ListNode h=new ListNode(0);
        ListNode res=h;
        // 左右链表是有序的
        while (left!=null&&right!=null){
            if(left.val<right.val){
                h.next=left;
                left=left.next;
            }else{
                h.next=right;
                right=right.next;
            }
            h=h.next;
        }
        h.next=left==null?right:left;

        return res.next;
    }
}
